package P2分治回溯;

import java.util.LinkedList;
import java.util.TreeSet;

public class FullPermutation {
    public static void main(String[] args) {
        String s = "ABC";
        char[] arr = s.toCharArray();
        TreeSet<String> set = new TreeSet<>();
        permutation(arr, 0, arr.length - 1, set);
        System.out.println(set);

        upperCase();
    }

    private static void upperCase() {
        String s = "131";
        char[] arr = s.toCharArray();
        LinkedList<String> list = new LinkedList<>();
        permutationUpper(arr, 0, arr.length - 1, list);
        System.out.println(list);
    }
    private static void permutationUpper(char[] arr, int from, int to, LinkedList<String> list) {
        if (from == to) {
            list.add(new String(arr));
        } else {
            for (int i = from; i <= to; i++) {
                if (check(arr,from,i)) {
                    swap(arr, i, from);
                    permutationUpper(arr, from + 1, to, list);
                    swap(arr, i, from);
                }
            }
        }
    }

    private static boolean check(char[] arr, int from, int i) {
        for (int k = from; k < i; k++) {
            if (arr[k] == arr[i]) {
                return false;
            }
        }
        return true;
    }

    private static void permutation(char[] arr, int from, int to, TreeSet<String> set) {
        if (from == to) {
            set.add(new String(arr));
        } else {
            for (int i = from; i <= to; i++) {
                swap(arr, i, from);
                permutation(arr, from + 1, to, set);
                swap(arr, i, from);
            }
        }
    }

    private static void swap(char[] arr, int i, int j) {
        char c = arr[i];
        arr[i] = arr[j];
        arr[j] = c;
    }
}